//
//  ProblemOffer59.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/12.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 59 - I. 滑动窗口的最大值 ✅
 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

 示例:
 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
 输出: [3,3,5,5,6,7]
 解释:

   滑动窗口的位置                最大值
 ---------------               -----
 [1  3  -1] -3  5  3  6  7       3
  1 [3  -1  -3] 5  3  6  7       3
  1  3 [-1  -3  5] 3  6  7       5
  1  3  -1 [-3  5  3] 6  7       5
  1  3  -1  -3 [5  3  6] 7       6
  1  3  -1  -3  5 [3  6  7]      7
  
 提示：
 你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
 */
@objcMembers class ProblemOffer59: NSObject {
    func solution() {
        print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
    }
    
    /*
     1: 创建一个数组deque，他是一个递减的队列:[5,3,2,-1], 当存放的却是在nums中对应的索引
     2: 滑动下一个窗口到位置nums[j]处，需要添加j到deque中，同时把最前一个值nums[i]移除：
        2.1: 添加nums[j]:
            从deque的尾部开始，删除所有比nums[j]小的值，因为只要j存在的一天，他们都不是最大
        2.2: 移除最前一个值nums[i]:
            2.2.1: 如果nums在[i-k, i]是一个递减的状态，例如：nums = [5, 3, 2, 1]，此时deque = [0, 1, 2], 那么当需要移除i==0的位置，那么deque[0]处肯定存储的是需要移除的i，所以判断 deque[0] == i-k
            2.2.2: 如果nums在[i-k, i]是不是一个递减的状态，nums有很多可能性：
                nums = [3, 4, 1, 2] deque = [1, 3]       因为递减的原因（3, 4）,被移除了
                nums = [3, 2, 1, 2] deque = [0, 1, 3]    判断deque[0] == i-k
            2.2.3 所以只需判断deque[0] == i-k，相等的话删除，不想等不需要处理，因为他递减的原因被移除了
     */
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        if nums.count == 0 || k == 0 {
            return []
        }
        if k == 1 {
            return nums
        }
        
        // 创建一个数组deque: 存放索引，他是一个递减的队列
        var deque = [Int]()
        // 创建一个数组result: 存放结果值
        var result = [Int]()
        
        for (i, num) in nums.enumerated() {
            // 来了一个值 num, 要把这个值放到队列中，那么要需要2步
            // 1: 删除掉用比num小的所有值
            while deque.isEmpty == false && num > nums[deque.last ?? 0] {
                _ = deque.popLast()
            }
            // 将元素添加到尾部
            deque.append(i)
            // 从deque中 删除 i-k 这个位置的数据
            if i - k >= -1, deque.isEmpty == false {
                if deque[0] == i-k {
                    deque.remove(at: 0)
                }
                // 3: 把这个num放入到队列中
                result.append(nums[deque[0]])
            }
        }
        
        return result
    }
    
}
